package algorithm.difficult;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: MinKBitFlips995
 * @description: 在仅包含 0 和 1 的数组 A 中，一次 K 位翻转包括选择一个长度为 K 的（连续）子数组，同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0。
 *
 * 返回所需的 K 位翻转的最小次数，以便数组没有值为 0 的元素。如果不可能，返回 -1。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-number-of-k-consecutive-bit-flips
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/2/2215:00
 * @since V1.0
 */
public class MinKBitFlips995 {
    /**
     *我们使用队列模拟滑动窗口，该滑动窗口的含义是前面 K−1K - 1K−1 个元素中，以哪些位置起始的 子区间 进行了翻转。该滑动窗口从左向右滑动，如果当前位置 iii 需要翻转，则把该位置存储到队列中。遍历到新位置 j(j<i+K)j (j < i + K)j(j<i+K) 时，队列中元素的个数代表了 iii 被前面 K−1K - 1K−1 个元素翻转的次数。
     *
     *     当 A[i]为 0，如果 i 位置被翻转了偶数次，那么翻转后仍是 0，当前元素需要翻转；
     *     当 A[i]为 1，如果 i 位置被翻转了奇数次，那么翻转后变成 0，当前元素需要翻转。
     *
     * 综合上面两点，我们得到一个结论，如果 len(que) % 2 == A[i] 时，当前元素需要翻转。
     *
     * 当 i+K>Ni + K > Ni+K>N 时，说明需要翻转大小为 K 的子区间，但是后面剩余的元素不到 K 个了，所以返回 -1。
     *
     * 作者：fuxuemingzhu
     * 链接：https://leetcode-cn.com/problems/minimum-number-of-k-consecutive-bit-flips/solution/hua-dong-chuang-kou-shi-ben-ti-zui-rong-z403l/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @Date: 2021/2/22 15:32
     */

    public int minKBitFlips(int[] A, int K) {
        Deque<Integer> que = new LinkedList<>();
        int res = 0;
        for (int i=0;i<A.length;i++){
            //如果队列第一个元素+K 大于等于当前下表，则弹出队列头部，因为此时头部的翻转并没有影响到这里了
            if (!que.isEmpty()&&que.getFirst()+K<=i){
                que.pollFirst();
            }
            //翻转
            if (que.size()%2==A[i]){
                //如果i在只剩K个数字的时候，还要翻转，说明后面的翻不够了。直接返回失败
                if (i+K>A.length) return -1;
                que.add(i);
                res++;
            }
        }
        return res;
    }
}
